Trails [A]

Memory limit: 32 MB

Byteasar is still playing with his plotter and printing bytecurves, see the task Plotter. (Recall that a bytecurve of order consists of segments of length each, the first of them connects the points and , and between any two consecutive segments the pen changes its direction by : the -th () turn is to the right if and only if for some integer and odd .) Byteasar has noticed that he can draw beautiful trails with his plotter. For this, before starting the plotter Byteasar sticks a piece of paper tape on the paper, so that it covers a rectangle with opposite vertices at coordinates and . After the plotter has completed printing, Byteasar can detach the tape and admire the beautiful trails on it. A trail is any connected curve of positive length plotted on the tape.

While waiting for the plotter to complete printing, Byteasar ponders how many trails will be plotted on the tape. Could you help him answer this question?

Input

The first line of the standard input contains two integers, and (), where indicates the order of the bytecurve and indicates the number of queries. The following lines contain three integers , and (, ) each that provide the coefficients the glued tape.

Output

Your program should output lines to the standard output - the answers to respective queries. Each line should hold a single integer - the number of trails drawn on the tape.

Example

For the input data:

4 3
-4 1 0
-4 -1 -2
-2 0 -4

the correct result is:

2
1
0

Task author: Tomasz Idziaszek.